#lang scribble/doc

@(require scribble/manual
          scribble/eval
          (for-label scheme)
          (for-label (prefix-in set: "set.ss"))
          (for-label (prefix-in bag: "bag.ss"))
          (for-label (prefix-in table: "table.ss"))
          (for-label srfi/67))

@title{Data Structures Galore}

@author[@author+email["Carl Eastlund" "cce@ccs.neu.edu"] 
        @author+email["Jens Axel Soegaard" "jensaxel@soegaard.net"]
        @author+email["Stevie Strickland" "sstrickl@ccs.neu.edu"]]

This library implements commonly used immutable data structures.  Currently
Galore provides:

@itemize[
@item{@as-index{Sets} (collections of distinct elements).}
@item{@as-index{Bags} (a.k.a. multi-sets, collections of elements).}
@item{@as-index{Tables} (finite mappings from distinct keys to arbitrary values).}
]

@(table-of-contents)

@section{Introduction}

This library implements commonly used immutable data structures.  Currently
Galore provides:

@itemize[
@item{@as-index{Sets} (collections of distinct elements).}
@item{@as-index{Bags} (a.k.a. multi-sets, collections of elements).}
@item{@as-index{Tables} (finite mappings from distinct keys to arbitrary values).}
]

(Other data structures provided by previous versions of Galore will be added in
time.  The previous versions of Galore will continue to be available in PLaneT.)

These data structures are immutable, meaning that no operation alters its
input.  Instead, each operation produces a new data structure, often sharing
some of its structure with its input.  This means that old values remain valid
until they are garbage collected and that these structures are safe for
multi-threaded programs.

Each data structure can have multiple implementations.  The primary module for
each data structure provides one or more constructors for each implementation,
and operations which work for any of the implementations.  Different
implementations may operate on different kinds of data, provide different
invariants, or have different time/space efficiency tradeoffs.

The operations for each data structure are provided by names describing only
their purpose (and not their kind of data structure).  To prevent clashes with
each other and with existing Scheme operations, it is recommended to import
these modules with a prefix:

@schemeblock[
(require (prefix-in set:   (planet soegaard/galore:4:1/set))
         (prefix-in bag:   (planet soegaard/galore:4:1/bag))
         (prefix-in table: (planet soegaard/galore:4:1/table)))]

Data structures are implemented in the MzScheme class system (see
documentation for @filepath{class.ss}).  Each kind of data structure
is an interface, each implementation is a class, and each operation is
a method.  Users can write their own implementation of Galore data
structures by writing classes that implement the given interfaces.  So
long as new implementations adhere to the interfaces and expected
invariants, the functions provided by Galore will work with them and
they will be interoperable with all other Galore data structures.

@subsection{Previous Versions}

Galore version 2 supports the following datastructures:
  @as-index{sets}, @as-index{bags}, @as-index{heaps}, @as-index{finite
  maps}, @as-index{priority queues}, @as-index{stacks},
  @as-index{queues}, @as-index{deques}.

For any datastructures or operations not yet provided by Galore version 3, use
the previous version:

@schemeblock[(require (planet "FILE.scm" ("soegaard" "galore.plt" 2)))]

The @PLaneT server contains the
@link["http://planet.plt-scheme.org/display.ss?package=galore.plt&owner=soegaard"]{documentation
and code} for the earlier versions of Galore.

@section{Sets}

@defmodule[(planet soegaard/galore:4:1/set)]

A set is a collection of elements.  

@defproc[(set? (v any/c)) boolean?]{ Predicate for sets. }

@defthing[set/c flat-contract?]{ Contract for sets of arbitrary objects. }

@deftogether[
(@defproc[(set-of/c (elem/c flat-contract?)) flat-contract?]
 @defproc[(non-empty-set-of/c (elem/c flat-contract?)) flat-contract?])]{
Contracts for sets whose contents match @scheme[elem/c]}

@subsection{Set Constructors}

A set implementation must have a way to distinguish its elements (how to tell
whether one element is the same as another).  Some implementations need to know
more about their elements, and use this to provide better invariants.

Each implementation provides two constructors.  The first accepts set elements
as additional arguments.  The second accepts set elements as a list.

Unordered sets require an equality predicate for their elements.  Most single
element operations will complete in linear time.  Unordered sets have two
constructors:

@deftogether[
(@defproc[(make-unordered (elem=? (-> any/c any/c boolean?)) (elem any/c) ...)
            set?]
 @defproc[(list->unordered (elem=? (-> any/c any/c boolean?)) (elems (listof any/c)))
            set?])]{
These operations construct a set containing the given elements as distinguished
by elem=?.}

Ordered sets require a total ordering for their elements.  These
orderings are represented as comparisons in the SRFI 67 style.  A
comparison produces @scheme[0] if its arguments are equal, @scheme[1]
if the first argument is greater, and @scheme[-1] if its second
argument is greater.  Most single element operations will complete in
logarithmic time.  Ordered sets have two constructors:

@deftogether[
(@defproc[(make-ordered (elem-compare (-> any/c any/c (integer-in -1 1)))
                        (elem any/c) ...) set?]
 @defproc[(list->ordered (elem-compare (-> any/c any/c (integer-in -1 1)))
                         (elems (listof any/c)))
          set?])]{
These operations construct a set containing the given elements as
distinguished by @scheme[elem-compare].  Operations which traverse the
set will traverse the elements in increasing order.}

Hashed sets group their elements by hash code; the hash function must respect
the given equality predicate (equal values must have the same hash code).
Operations will take time logarithmic in the number of distinct hash codes and
linear in the number of elements in a single hash code.  Hashed sets have two
constructors:

@deftogether[
(@defproc[(make-hashed (elem-hash (-> any/c integer?)) 
                       (elem=? (-> any/c any/c boolean?))
                       (elem any/c) ...) set?]
 @defproc[(list->hashed (elem-hash (-> any/c integer?)) 
                        (elem=? (-> any/c any/c boolean?))
                        (elems (listof any/c)))
          set?])]{

These operations construct a set containing the given elements as
distinguished by @scheme[elem=?].}

Galore also provides six shortcut constructors for sets whose elements are
distinguished by the standard Scheme comparisons eq?, eqv?, and equal?.

@deftogether[
(@defproc[(make-eq (elem any/c) ...) set?]
 @defproc[(list->eq (elems (listof any/c))) set?])]{
These operations construct a hashed set containing the given elements
as distinguished by eq?.}

@deftogether[
(@defproc[(make-eqv (elem any/c) ...) set?]
 @defproc[(list->eqv (elems (listof any/c))) set?])]{
These operations construct an unordered set containing the given
elements as distinguished by eqv?.}

@deftogether[
(@defproc[(make-equal (elem any/c) ...) set?]
 @defproc[(list->equal (elems (listof any/c))) set?])]{
These operations construct a hashed set containing the given elements
as distinguished by equal?.}

@subsection{Set Accessors}

These operations extract information from a set.

@defproc[(elements (set set?)) (listof any/c)]{
Produces a list of all of @scheme[set]'s elements.  The elements are
in increasing order for ordered sets.}

@defproc[(empty? (set set?)) boolean?]{
Reports whether @scheme[set] contains no elements.}

@defproc[(size (set set?)) natural-number/c]{
Produces the number of elements in @scheme[set].}

@defproc[(member? (elem any/c) (set set?)) boolean?]{
Reports whether @scheme[set] contains @scheme[elem].}

@defproc[(lookup (elem any/c)
                 (set set?)
                 (failure-thunk (-> any) (lambda () #f))
                 (success-function (-> any/c any) (lambda (e) e)))
         any/c]{

Finds an element in @scheme[set] that is equal to @scheme[elem].  If
such an element @scheme[e] is found, lookup produces
@scheme[(success-function e)].  If no such element is found, lookup
produces @scheme[(failure-thunk)].  The default success-function
returns @scheme[e].  The default failure-thunk returns @scheme[#f].}

@defproc[(select (set set?)) any/c]{
Produces an element from the non-empty set. It is unspecified which
element is produced.}

@subsection{Set Updaters}

These operations construct updated forms of their input set.  The result is
always of the same implementation as the input.

@defproc[(insert (elem any/c) (set set?)) set?]{
Produces a @scheme[set] containing @scheme[elem] and all elements of
@scheme[set].}

@defproc[(remove (elem any/c) (set set?)) set?]{
Produces a set containing all elements of @scheme[set] except
@scheme[elem].}

@defproc[(clear (set set?)) set?]{
Produces an empty set.}

@subsection{Set Traversals}

These operations work on each element of a set.  Each traversal works on
elements in the same order they are produced by the elements operation.

@defproc[(fold (combine (-> any/c any/c any))
               (init any/c)
               (set set?))
         any/c]{

Builds a result from set's elements.  If @scheme[(elements set)] is
@scheme[(list e1 e2 ... en)], the result is @scheme[(combine en
... (combine e2 (combine e1 init))...)].}

@defproc[(map (transform (-> any/c any))
              (set set?))
         set?]{
Produces a new set containing the transformed image of each element of
@scheme[set].}

@defproc[(for-each (action (-> any/c any))
                   (set set?))
         any/c]{
Calls @scheme[action] for each element of @scheme[set].}

@defproc[(filter (predicate (-> any/c boolean?))
                 (set set?))
         set?]{
Produces a set containing the elements of @scheme[set] that satisfy
@scheme[predicate].  The result is of the same implementation as
@scheme[set].}

@deftogether[
(@defproc[(all? (predicate (-> any/c boolean?))
                (set set?))
          boolean?]
 @defproc[(andmap (predicate (-> any/c boolean?))
                  (set set?))
          boolean?])]{
Reports whether all elements of @scheme[set] satify
@scheme[predicate].  These operations are synonymous.}

@deftogether[
(@defproc[(any? (predicate (-> any/c boolean?))
                (set set?))
          boolean?]
 @defproc[(ormap (predicate (-> any/c boolean?))
                 (set set?))
          boolean?])]{
Reports whether any element of @scheme[set] satisfies
@scheme[predicate].  These operations are synonymous.}

@subsection[#:tag "Subsec:SetCombinations"]{Set Combinations}

These operations represent set-theoretic operations combining multiple sets.  In
all cases, the result is of the same implementation as the first set argument.

Multiple sets may only be combined if their notions of distinct elements are the
same.  If two sets with different equality are combined the result will be
unpredictable and may yield an error.  Here are some concrete examples:

@itemize[

@item{@scheme[(make-unordered = 1 2 3)] and @scheme[(make-ordered
  number-compare 4 5 6)] may be combined, because @scheme[=] and
  @scheme[number-compare] represent the same equality relation.  Both
  will distinguish numbers based on numerical equivalence.}  

@item{@scheme[(make-equal "A" "B" "C")] and @scheme[(make-eq "A" "B"
  "C")] may not be combined, because @scheme[equal?] and @scheme[eq?]
  do not represent the same equality relation.  Specifically, it is
  ambiguous whether both @scheme["A"]s represent equivalent
  elements.}]

@defproc[(union (set1 set?) (set2 set?)
                (combine (-> any/c any/c any)
                         (lambda (e1 e2) e1)))
         set?]{

Produces a set containing all elements present in either @scheme[set1]
or @scheme[set2].  If @scheme[set1] and @scheme[set2] contain
equivalent elements @scheme[e1] and @scheme[e2] respectively, union
adds @scheme[(combine e1 e2)] to the result in their place.  The
default combine returns @scheme[e1].}

@defproc[(intersection (set1 set?)
                       (set2 set?)
                       (combine (-> any/c any/c any)
                                (lambda (e1 e2) e1)))
         set?]{

Produces a set containing all elements present in both @scheme[set1]
and @scheme[set2].  For each pair of equivalent elements @scheme[e1]
and @scheme[e2] found in @scheme[set1] and @scheme[set2] respectively,
intersection adds @scheme[(combine e1 e2)] to the result.  The default
@scheme[combine] returns @scheme[e1].}

@defproc[(difference (set1 set?) (set2 set?)) set?]{
Produces a set containing all elements of @scheme[set1] not found in
@scheme[set2].}

@subsection{Set Relations}

These operations compare multiple sets.  As in
@secref["Subsec:SetCombinations"], multiple sets may only be
meaningfully compared if their notions of distinct elements are the
same.

@defproc[(subset? (set1 set?) (set2 set?)) boolean?]{
Reports whether all elements in @scheme[set1] are present in
@scheme[set2].}

@defproc[(equal? (set1 set?) (set2 set?)) boolean?]{
Reports whether both sets contain the same elements.}

@subsection{Sets and Eager Comprehensions}

@defmodule[(planet soegaard/galore:4:1/comprehensions)]

Support for srfi-42 eager comprehensions are provided by
@filepath{comprehensions.ss}'s comprehension @scheme[set-ec] and
generator @scheme[:set].

@defform[(set-ec empty-expr qualifier ... expr)]{
The comprehension @scheme[set-ec] evaluates the expression
@scheme[empty-expr] whose result must be an empty set. Then the values
obtained by evaluating @scheme[expr] once for each binding are
inserted into the set. If there are no qualifiers the result is a
singleton set whose element is the result of evaluating
@scheme[expr].}

@defform[(:set var arg)]{
The generator @scheme[:set] runs through the elements in a set. First
@scheme[arg] is evaluated then the variable @scheme[var] is bound to
each element of the set in turn. The effect of assigning a value to
@scheme[var] is undefined.}

An example:

@interaction[
(require (prefix-in set: (planet "set.ss" ("soegaard" "galore.plt" 4 1)))
         (planet "comprehensions.ss" ("soegaard" "galore.plt" 4 1))
         (lib "42.ss" "srfi")
         (lib "67.ss" "srfi"))
(define a-set
  (set-ec (set:make-ordered integer-compare)
          (:range i -5 5)
          (* i i)))
(set:elements a-set)
(list-ec (:set x a-set)
         x)
(list-ec (: x a-set)
         x)]

@section{Tables}

@defmodule[(planet soegaard/galore:4:1/table)]

A @deftech{table} is a finite mapping from distinct keys to distinct
values.  A single key/value pair in a table is called a
@deftech{binding}.

Galore provides the following operations for creating and manipulating
tables.

@subsection{Table Predicates}

These operations determine whether values are tables.

@defproc[(table? (v any/c)) boolean?]{Basic predicate for tables.}

@deftogether[
(@defthing[table/c flat-contract?]
 @defthing[non-empty-table/c flat-contract?])]{
These contracts accept tables.  The @scheme[non-empty-table/c]
contract requires tables to contain at least one binding.}

@deftogether[
(@defproc[(table-of/c (key/c flat-contract?) 
                      (value/c flat-contract?))
          flat-contract?]
 @defproc[(non-empty-table-of/c (key/c flat-contract?)
                                (value/c flat-contract?))
          flat-contract?])]{
These produce a contract that accepts tables of with bindings matching
the given contracts.  The result of @scheme[non-empty-table-of/c]
requires tables to contain at least one binding.}

@subsection{Table Constructors}

A table implementation must be able to distinguish its keys just like a set
implementation must distinguish its elements.  Like sets, tables have different
implementations that require different information about their keys.

Each implementation provides four constructors.  The first accepts bindings as
additional arguments, alternating keys and values.  The second accepts bindings
as an s-expression: a list of two-element lists, each a key followed by a
value.  The third accepts bindings as an association list of key/value pairs.
The last accepts bindings as a list of keys and a separate list of their
respective values.

@deftogether[
(@defproc[(make-unordered (key=? (-> any/c any/c boolean?))
                          (key any/c)
                          (value any/c) 
                          ...)
          table?]
 @defproc[(sexp->unordered (key=? (-> any/c any/c boolean?))
                           (sexp (listof (listof any/c any/c))))
          table?]
 @defproc[(alist->unordered (key=? (-> any/c any/c boolean?))
                            (alist (listof (cons/c any/c any/c))))
          table?]
 @defproc[(lists->unordered (key=? (-> any/c any/c boolean?))
                            (keys (listof any/c))
                            (values (listof any/c)))
          table?])]{

Unordered tables require an equality predicate for their keys.  Most
single-binding operations will complete in linear time.  Keys are
distinguished by @scheme[key=?].}

@deftogether[
(@defproc[(make-ordered (key-compare (-> any/c any/c (integer-in -1 1)))
                        (key any/c)
                        (value any/c)
                        ...)
          table?]
 @defproc[(sexp->ordered (key-compare (-> any/c any/c (integer-in -1 1)))
                         (sexp (listof (listof any/c any/c))))
          table?]
 @defproc[(alist->ordered (key-compare (-> any/c any/c (integer-in -1 1)))
                          (alist (listof (cons/c any/c any/c))))
          table?]
 @defproc[(lists->ordered (key-compare (-> any/c any/c (integer-in -1 1)))
                          (keys (listof any/c))
                          (values (listof any/c)))
          table?])]{

Ordered tables require a total ordering for their keys.  These
orderings are represented as comparisons in the SRFI 67 style (see
description for ordered sets, above).  Most single-binding operations
will complete in logarithmic time.  Operations which traverse the
table will traverse the bindings in increasing order of their keys.}

@deftogether[
(@defproc[(make-hashed (key-hash (-> any/c integer?))
                       (key=? (-> any/c any/c boolean?))
                       (key any/c)
                       (value any/c)
                       ...)
          table?]
 @defproc[(sexp->hashed (key-hash (-> any/c integer?))
                        (key=? (-> any/c any/c boolean?))
                        (sexp (listof (listof any/c any/c))))
          table?]
 @defproc[(alist->hashed (key-hash (-> any/c integer?))
                         (key=? (-> any/c any/c boolean?))
                         (alist (listof (cons/c any/c any/c))))
          table?]
 @defproc[(lists->hashed (key-hash (-> any/c integer?))
                         (key=? (-> any/c any/c boolean?))
                         (keys (listof any/c))
                         (values (listof any/c)))
          table?])]{

Hashed tables group their keys by hash code; the hash function must
respect the given equality predicate (equal keys must have the same
hash code).  Operations will take time logarithmic in the number of
distinct hash codes and linear in the number of keys in a single hash
code.  These operations construct a table containing the given
bindings with keys distinguished by @scheme[key=?].  }

@deftogether[
(@defproc[(make-eq (key any/c) (value any/c) ...) table?]
 @defproc[(sexp->eq (sexp (listof (listof any/c any/c)))) table?]
 @defproc[(alist->eq (alist (listof (cons/c any/c any/c)))) table?]
 @defproc[(lists->eq (keys (listof any/c)) (values (listof any/c))) table?]
 @defproc[(make-eqv (key any/c) (value any/c) ...) table?]
 @defproc[(sexp->eqv (sexp (listof (listof any/c any/c)))) table?]
 @defproc[(alist->eqv (alist (listof (cons/c any/c any/c)))) table?]
 @defproc[(lists->eqv (keys (listof any/c)) (values (listof any/c))) table?]
 @defproc[(make-equal (key any/c) (value any/c) ...) table?]
 @defproc[(sexp->equal (sexp (listof (listof any/c any/c)))) table?]
 @defproc[(alist->equal (alist (listof (cons/c any/c any/c)))) table?]
 @defproc[(lists->equal (keys (listof any/c)) (values (listof any/c))) table?])]{

Galore also provides shortcut constructors for tables whose keys are
distinguished by the standard Scheme comparisons @scheme[eq?],
@scheme[eqv?], and @scheme[equal?].}

@subsection{Table Accessors}

@defproc[(keys (table table?)) (listof any/c)]{

Produces a list of @scheme[table]'s keys.  For ordered tables, the
keys are sorted from least to greatest.}

@defproc[(values (table table?)) (listof any/c)]{

Produces a list of @scheme[table]'s values.  The values appear in the
same order as their respective keys in @scheme[(keys table)].}

@defproc[(to-sexp (table table?)) (listof (listof any/c any/c))]{

Produces a list of table's bindings as two-element lists, each a key
followed by its value.  The bindings appear in the same order as their
respective keys in @scheme[(keys table)].}

@defproc[(empty? (table table?)) boolean?]{@scheme[#f] unless
@scheme[table] is empty}

@defproc[(size (table table?)) natural-number/c]{Produces the number
of bindings in @scheme[table].}

@defproc[(contains? (key any/c) (table table?)) boolean?]{Reports
whether table contains @scheme[key].}

@defproc[(lookup (key any/c)
                 (table table?)
                 (failure-thunk (-> any) (lambda () #f))
                 (success-function (-> any/c any) (lambda (value) value)))
         any/c]{

Looks up the value bound to @scheme[key] in table.  If such a value
@scheme[v] is found, lookup produces @scheme[(success-function v)].
If no such value is found, lookup produces @scheme[(failure-thunk)].
The default @scheme[success-function] returns @scheme[v].  The default
@scheme[failure-thunk] returns @scheme[#f].}

@defproc[(lookup/key (key any/c)
                     (table table?)
                     (failure-thunk (-> any) (lambda () #f))
                     (success-function (-> any/c any/c any) (lambda (key value) key)))
         table?]{

Looks up the binding for @scheme[key] in table.  If a binding of
@scheme[k] to @scheme[v] is found, @scheme[lookup/key] produces
@scheme[(success-function k v)].  If no such binding is found,
@scheme[lookup/key] produces @scheme[(failure-thunk)].  The default
@scheme[success-function] returns @scheme[k].  The default
@scheme[failure-thunk] returns @scheme[#f].}

@deftogether[
(@defproc[(select (table table?)) (values any/c any/c)]
 @defproc[(select/key (table table?)) any/c]
 @defproc[(select/value (table table?)) any/c])]{

These operations select a binding from a non-empty table, returning
its key, value, or both as appropriate.  It is not specified which
binding is chosen.}

@subsection{Table Updaters}

These operations construct updated forms of their input table.  The
result is always of the same implementation as the input.

@defproc[(insert (key any/c) (value any/c) (table table?)) table?]{

Produces a table in which @scheme[key] is bound to @scheme[value] and
containing all other bindings of @scheme[table].}

@defproc[(remove (key any/c) (table table?)) table?]{

Produces a table containing all bindings of @scheme[table] except any
binding for @scheme[key].}

@defproc[(update (key any/c) (transform (-> any/c any/c any)) (table table?)) table?]{

Produces a table with all bindings of @scheme[table] except any
binding for @scheme[key].  If @scheme[table] maps @scheme[k] to
@scheme[v] (with @scheme[k] equal to @scheme[key]), the result maps
@scheme[k] to @scheme[(transform k v)].  If @scheme[table] has no
binding for @scheme[key], the result has none.}

@defproc[(update/value (key any/c) (transform (-> any/c any)) (table table?)) table?]{

As @scheme[update], but produces a new value based only on the
previous value.}

@defproc[(update/insert (key any/c) 
                        (transform (-> any/c any/c any)) 
                        (value any/c)
                        (table table?))
         table?]{

Produces a table with all bindings of @scheme[table] except any
binding for @scheme[key].  If table maps @scheme[key] to @scheme[v],
the result maps @scheme[key] to @scheme[(transform v)].  If table has
no binding for @scheme[key], the result maps @scheme[key] to
@scheme[value].}

@defproc[(update/insert/value (key any/c)
                              (transform (-> any/c any))
                              (value any/c)
                              (table table?))
         table?]{

As @scheme[update/insert], but produces a new value based only on the
previous value.}

@defproc[(clear (table table?)) table?]{ Produces an empty table.} 

@subsection{Table Traversals}

These operations work on each binding of a table.  Each traversal
works on bindings in the same order their keys are produced by the
@scheme[keys] operation.  Each traversal has three forms.  The basic
form processes they key and value of each binding.  The @scheme[/key]
form processes only the key of each binding.  The @scheme[/value] form
processes only the value of each binding.

@deftogether[
(@defproc[(fold (combine (-> any/c any/c any/c any))
                (init any/c)
                (table table?))
          any/c]
 @defproc[(fold/key (combine/key (-> any/c any/c any))
                    (init any/c)
                    (table table?))
          any/c]
 @defproc[(fold/value (combine/value (-> any/c any/c any))
                      (init any/c)
                      (table table?))
          any/c])]{

These operations build a result from table's bindings.  If
@scheme[(keys table)] produces @scheme[(list k1 k2 ... kn)] and
@scheme[(values table)] produces @scheme[(list v1 v2 ... vn)], the
respective results will be:
@schemeblock[
(combine kn vn ... (combine k2 v2 (combine k1 v1 init))...)
(combine/key kn ... (combine/key k2 (combine/key k1 init))...)
(combine/value vn ... (combine/value v2 (combine/value v1 init))...)]}

@deftogether[
(@defproc[(for-each (action (-> any/c any/c any))
                    (table table?))
          any/c]
 @defproc[(for-each/key (action/key (-> any/c any))
                        (table table?))
          any/c]
 @defproc[(for-each/value (action/value (-> any/c any))
                          (table table?))
          any/c])]{

These operations call @scheme[action] (or @scheme[action/key] or
@scheme[action/value]) for each binding in @scheme[table].}

@deftogether[
(@defproc[(map (transform (-> any/c any/c any))
               (table table?))
          table?]
 @defproc[(map/key (transform/key (-> any/c any))
                   (table table?))
          table]
 @defproc[(map/value (transform/value (-> any/c any))
                     (table table?))
          table])]{

These operations produce a table binding each key from @scheme[table]
to the image of the previous binding produced by @scheme[transform]
(or @scheme[transform/key] or @scheme[transform/value]).  The result
is of the same implementation as @scheme[table].}

@deftogether[
(@defproc[(filter (predicate (-> any/c any/c boolean?))
                  (table table?))
          table?]
 @defproc[(filter/key (predicate/key (-> any/c boolean?))
                      (table table?))
          table?]
 @defproc[(filter/value (predicate/value (-> any/c boolean?))
                        (table table?))
          table?])]{

These operations produce a table containing each binding in
@scheme[table] that satisfies @scheme[predicate] (or
@scheme[predicate/key] or @scheme[predicate/value]).  The result is of
the same implementation as @scheme[table].}

@deftogether[
(@defproc[(all? (predicate (-> any/c any/c boolean?))
                (table table?))
          table?]
 @defproc[(all?/key (predicate/key (-> any/c boolean?))
                    (table table?))
          table?]
 @defproc[(all?/value (predicate/value (-> any/c boolean?))
                      (table table?))
          table?]
 @defproc[(andmap (predicate (-> any/c any/c boolean?))
                  (table table?))
          table?]
 @defproc[(andmap/key (predicate/key (-> any/c boolean?))
                      (table table?))
          table?]
 @defproc[(andmap/value (predicate/value (-> any/c boolean?))
                        (table table?))
          table?])]{

Reports whether all bindings of @scheme[table] satisfy
@scheme[predicate] (or @scheme[predicate/key] or
@scheme[predicate/value]).  The @scheme[all?] variants are synonymous
with the @scheme[andmap] variants.}

@deftogether[
(@defproc[(any? (predicate (-> any/c any/c boolean?))
                (table table?))
          table?]
 @defproc[(any?/key (predicate/key (-> any/c boolean?))
                    (table table?))
          table?]
 @defproc[(any?/value (predicate/value (-> any/c boolean?))
                      (table table?))
          table?]
 @defproc[(ormap (predicate (-> any/c any/c boolean?))
                (table table?))
          table?]
 @defproc[(ormap/key (predicate/key (-> any/c boolean?))
                     (table table?))
          table?]
 @defproc[(ormap/value (predicate/value (-> any/c boolean?))
                       (table table?))
          table?])]{

Reports whether any binding of @scheme[table] satisfies
@scheme[predicate] (or @scheme[predicate/key] or
@scheme[predicate/value]).  The @scheme[any?] variants are synonmous
with the @scheme[ormap] variants.  }

@subsection[#:tag "Subsec:TableCombinations"]{Table Combinations}

These operations mimic set operations combining the bindings of multiple tables
by their corresponding keys.  In all cases, the result is of the same
implementation as the first table argument.

Multiple tables may only be combined if their notion of distinct keys
are the same.  If two tables with different equality are combined the
result will be unpredictable and may yield an error.  For concrete
examples, see @secref["Subsec:SetCombinations"] above.

@deftogether[
(@defproc[(union (table1 table?) 
                 (table2 table?)
                 (combine (-> any/c any/c any/c any) 
                          (lambda (key value1 value2) value1)))
          table?]
 @defproc[(union/value 
           (table1 table?)
           (table2 table?)
           (combine/value (-> any/c any/c any)
                          (lambda (value1 value2) value1)))
          table?])]{

These operations produce a table containing all bindings present in
either @scheme[table1] or @scheme[table2].  If @scheme[table1] and
@scheme[table2] bind key @scheme[k] to values @scheme[v1] and
@scheme[v2] respectively, @scheme[union] binds @scheme[k] to
@scheme[(combine k v1 v2)] and @scheme[union/value] binds @scheme[k]
to @scheme[(combine/value v1 v2)] in the result.}

@deftogether[
(@defproc[(intersection (table1 table?)
                        (table2 table?)
                        (combine (-> any/c any/c any/c any)
                                 (lambda (key value1 value2) value1)))
          table?]
 @defproc[(intersection/value (table1 table?)
                              (table2 table?)
                              (combine/value (-> any/c any/c any)
                                       (lambda (key value1 value2) value1)))
          table?])]{

These operations produce a table containing all bindings present in
both @scheme[table1] and @scheme[table2].  For each key @scheme[k]
bound to values @scheme[v1] and @scheme[v2] in @scheme[table1] and
@scheme[table2] respectively, @scheme[intersection] binds @scheme[k]
to @scheme[(combine k v1 v2)] and @scheme[intersection/value] binds
@scheme[k] to @scheme[(combine/value v1 v2)] in the result.}

@defproc[(difference (table1 table?) (table2 table?)) table?]{Produces
a table containing all bindings of table1 whose key is not in table2.}

@subsection{Table Relations}

These operations compare multiple tables.  As in
@secref["Subsec:TableCombinations"], multiple tables may only be
meaningfully compared if their notions of distinct keys are the same.

@defproc[(subtable? (value=? (-> any/c any/c boolean?))
                    (table1 table?)
                    (table2 table?))
         boolean?]{

Reports whether all keys in @scheme[table1] are present in
@scheme[table2], and that the values bound to each key in both tables
are the same with respect to @scheme[value=?].}

@defproc[(equal? (value=? (-> any/c any/c boolean?))
                 (table1 table?)
                 (table2 table?))
         table?]{

Reports whether both tables contain the same keys, and that the values
bound to each key in both tables are the same with respect to
@scheme[value=?].}


@section{Bags}

@defmodule[(planet soegaard/galore:4:1/bag)]

A @deftech{bag} is a collection of elements.  Unlike sets, the
elements in a bag need not be distinct.

Galore provides the following operations for creating and manipulating bags.

@subsection{Bag Predicates}

@defproc[(bag? (v any/c)) boolean?]{Reports whether @scheme[v] is a bag.}

@deftogether[
(@defthing[bag/c flat-contract?]
 @defthing[non-empty-bag/c flat-contract?])]{

These contracts accept bags.  The @scheme[non-empty-bag/c] contract
requires bags to contain at least one element.}

@deftogether[
(@defproc[(bag-of/c (elem/c flat-contract?)) flat-contract?]
 @defproc[(non-empty-bag-of/c (elem/c flat-contract?)) flat-contract?])]{

These produce a contract that accepts bags, where @scheme[elem/c]
accepts elements.  The result of @scheme[non-empty-bag-of/c] requires
bags to contain at least one element.}

@subsection{Bag Constructors}

A bag implementation must have a way to distinguish its elements (how to tell
whether one element is the same as another).  Some implementations need to know
more about their elements, and use this to provide better invariants.

Each implementation provides two constructors.  The first accepts bag elements
as additional arguments.  The second accepts bag elements as a list.

@deftogether[
(@defproc[(make-unordered (elem=? (-> any/c any/c boolean?))
                          (elem any/c) ...)
          bag?]
 @defproc[(list->unordered (elem=? (-> any/c any/c boolean?))
                           (elems (listof any/c)))
          bag?])]{

Unordered bags require an equality predicate for their elements.  Most
single element operations will complete in linear time.  These
operations construct a bag containing the given elements as
distinguished by @scheme[elem=?].}

@deftogether[
(@defproc[(make-ordered (elem-compare (-> any/c any/c (integer-in -1 1)))
                        (elem any/c) ...)
          bag?]
 @defproc[(list->ordered (elem-compare (-> any/c any/c (integer-in -1 1)))
                         (elems (listof any/c)))
          bag?])]{

Ordered bags require a total ordering for their elements.  These
orderings are represented as comparisons in the SRFI 67 style.  A
comparison produces @scheme[0] if its arguments are equal, @scheme[1]
if the first argument is greater, and @scheme[-1] if its second
argument is greater.  Most single element operations will complete in
logarithmic time.  These operations construct a bag containing the
given elements as distinguished by @scheme[elem-compare].  Operations
which traverse the bag will traverse the elements in increasing
order.}

@deftogether[
(@defproc[(make-hashed (elem-hash (-> any/c integer?))
                       (elem=? (-> any/c any/c boolean?))
                       (elem any/c) ...)
          bag?]
 @defproc[(list->hashed (elem-hash (-> any/c integer?))
                        (elem=? (-> any/c any/c boolean?))
                        (elems (listof any/c)))
          bag?])]{

Hashed bags group their elements by hash code; the hash function must
respect the given equality predicate (equal values must have the same
hash code).  Operations will take time logarithmic in the number of
distinct hash codes and linear in the number of elements in a single
hash code.  These operations construct a bag containing the given
elements as distinguished by @scheme[elem=?].}

@deftogether[
(@defproc[(make-eq (elem any/c) ...) bag?]
 @defproc[(list->eq (elems (listof any/c))) bag?]
 @defproc[(make-eqv (elem any/c) ...) bag?]
 @defproc[(list->eqv (elems (listof any/c))) bag?]
 @defproc[(make-equal (elem any/c) ...) bag?]
 @defproc[(list->equal (elems (listof any/c))) bag?])]{

Galore also provides six shortcut constructors for bags whose elements
are distinguished by the standard Scheme comparisons @scheme[eq?],
@scheme[eqv?], and @scheme[equal?].}

@subsection{Bag Accessors}

These operations extract information from a bag.

@defproc[(elements (bag bag?)) (listof any/c)]{Produces a list of all
of the @scheme[bag]'s elements.  The elements are in increasing order
for ordered bags.}

@defproc[(to-sexp (bag bag?)) (listof (list any/c natural-number/c))]{

Produces a list of lists where each list contains an element of the
@scheme[bag] and how many times that element appears in the
@scheme[bag].  The ordering is the same as for @scheme[(elements
bag)].}

@defproc[(to-alist (bag bag?)) (listof (cons/c any/c natural-number/c))]{

Produces a list of pairs where each pair contains an element of the
@scheme[bag] and how many times that element appears in the
@scheme[bag].  The ordering is the same as for @scheme[(elements
bag)].}

@defproc[(empty? (bag bag?)) boolean?]{Reports whether bag contains no
elements.}

@defproc[(size (bag bag?)) natural-number/c]{Produces the number of
elements in bag.}

@defproc[(size/unique (bag bag?)) natural-number/c]{Produces the
number of distinct elements in the bag.}

@defproc[(member? (elem any/c) (bag bag?)) boolean?]{Reports whether
bag contains elem.}

@defproc[(count (elem any/c) (bag bag?)) natural-number/c]{Produces
the number of times the element appears in the bag.  If it does not,
then @scheme[0] is produced.}

@defproc[(lookup (elem any/c) 
                (bag bag?)
                (failure-thunk (-> any) (lambda () #f))
                (success-function (-> any/c any) (lambda (e) e)))
         any/c]{

Finds an element in @scheme[bag] that is equal to @scheme[elem].  If
such an element @scheme[e] is found, @scheme[lookup] produces
@scheme[(success-function e)].  If no such element is found,
@scheme[lookup] produces @scheme[(failure-thunk)].  The default
@scheme[success-function] returns @scheme[e].  The default
@scheme[failure-thunk] returns @scheme[#f].}

@defproc[(lookup/count (elem any/c)
                       (bag bag?)
                       (failure-thunk (-> any)
                                      (lambda () #f))
                       (success-function (-> any/c
                                             natural-number/c
                                             any)
                                         (lambda (e c) e)))
         any/c]{

Finds an element in @scheme[bag] that is equal to @scheme[elem].  If
such an element @scheme[e] is found, @scheme[lookup/count] produces
@scheme[(success-function e c)] (where @scheme[c] is the element's
count).  If no such element is found, @scheme[lookup/count] produces
@scheme[(failure-thunk)].  The default @scheme[success-function]
returns @scheme[e].  The default @scheme[failure-thunk] returns
@scheme[#f].}

@defproc[(select (bag bag?)) any/c]{Produces an element from the
non-empty @scheme[bag]. It is unspecified which element is produced.}

@defproc[(select/count (bag bag?)) (values any/c natural-number/c)]{

Produces an element and its count from the non-empty @scheme[bag]. It
is unspecified which element is produced.}

@subsection{Bag Updaters}

These operations construct updated forms of their input bag.  The result is
always of the same implementation as the input.

@defproc[(insert (elem any/c)
                 (bag bag?))
         bag?]{

Produces a bag containing all elements of @scheme[bag], plus one more
occurrence of @scheme[elem].}

@defproc[(insert/count (elem any/c)
                       (count natural-number/c)
                       (bag bag?))
         bag?]{

Produces a bag containing all elements of @scheme[bag], plus
@scheme[n] more occurrences of @scheme[elem].}

@defproc[(remove (elem any/c)
                 (bag bag?))
         bag?]{

Produces a bag containing all elements of @scheme[bag] except one less
occurence of @scheme[elem], or no occurrences if @scheme[bag] had
none.}

@defproc[(remove/count (elem any/c)
                       (n natural-number/c)
                       (bag bag?))
         bag?]{

Produces a bag containing all elements of @scheme[bag] except
@scheme[n] fewer occurrences of @scheme[elem], or no occurrences if
there were less than @scheme[n] occurrences.}

@defproc[(clear (bag bag?)) bag?]{Produces an empty bag.}

@subsection{Bag Traversals}

These operations work on each element of a bag.  Each traversal works
on elements in the same order they are produced by the elements
operation.

@deftogether[
(@defproc[(fold (combine (-> any/c any/c any))
               (init any/c)
               (bag bag?))
         any/c]
 @defproc[(fold/count (combine (-> any/c natural-number/c any/c any))
                     (init any/c)
                     (bag bag?))
         any/c])]{

Builds a result from @scheme[bag]'s elements.  If @scheme[(elements
bag)] is @scheme[(list e1 e2 ... en)], the result is @scheme[(combine
en ... (combine e2 (combine e1 init))...)].}

@deftogether[
(@defproc[(map (transform (-> any/c any))
              (bag bag?))
         bag?]
 @defproc[(map/count (transform (-> any/c natural-number/c any))
                    (bag bag?))
         bag?])]{

Produces a new bag containing the transformed image of each element of
the bag.}

@deftogether[
(@defproc[(for-each (action (-> any/c any))
                   (bag bag?))
         bag?]
 @defproc[(for-each/count (action (-> any/c natural-number/c any))
                         (bag bag?))
         bag?])]{

Calls @scheme[action] for each element of @scheme[bag].}

@deftogether[
(@defproc[(filter (predicate (-> any/c boolean?))
                  (bag bag?))
          bag?]
 @defproc[(filter/count (predicate/count (-> any/c natural-number/c boolean?))
                        (bag bag?))
          bag?])]{

Produces a bag containing the elements of @scheme[bag] that satisfy
@scheme[predicate].  The result is of the same implementation as bag.}

@deftogether[
(@defproc[(all? (predicate (-> any/c boolean?))
                (bag bag?))
          boolean?]
 @defproc[(andmap (predicate (-> any/c boolean?))
                  (bag bag?))
          boolean?]
 @defproc[(all?/count (predicate/count (-> any/c natural-number/c boolean?))
                      (bag bag?))
          boolean?]
 @defproc[(andmap/count (predicate/count (-> any/c natural-number/c boolean?))
                        (bag bag?))
          boolean?])]{

Reports whether all elements of bag satify predicate.}

@deftogether[
(@defproc[(any? (predicate (-> any/c boolean?))
                (bag bag?))
          boolean?]
 @defproc[(ormap (predicate (-> any/c boolean?))
                 (bag bag?))
          boolean?]
 @defproc[(any?/count (predicate/count (-> any/c natural-number/c boolean?))
                      (bag bag?))
          boolean?]
 @defproc[(ormap/count (predicate/count (-> any/c natural-number/c boolean?))
                       (bag bag?))
          boolean?])]{

Reports whether any element of bag satisfies predicate.}

@subsection[#:tag "Subsec:BagCombinations"]{Bag Combinations}

These operations represent bag-theoretic operations combining multiple
bags.  In all cases, the result is of the same implementation as the
first bag argument.

Multiple bags may only be combined if their notions of distinct
elements are the same.  If two bags with different equality are
combined the result will be unpredictable and may yield an error.
Here are some concrete examples:

@itemize[

@item{@scheme[(make-unordered = 1 2 3)] and @scheme[(make-ordered
  number-compare 4 5 6)] may be combined, because @scheme[=] and
  @scheme[number-compare] represent the same equality relation.  Both
  will distinguish numbers based on numerical equivalence.}

@item{@scheme[(make-equal "A" "B" "C")] and @scheme[(make-eq "A" "B"
  "C")] may not be combined, because @scheme[equal?] and @scheme[eq?]
  do not represent the same equality relation.  Specifically, it is
  ambiguous whether both @scheme["A"]s represent equivalent elements.}]

@defproc[(union (bag1 bag?) (bag2 bag?)) bag?]{Produces a bag
containing all elements present in either @scheme[bag1] or
@scheme[bag2].  If @scheme[bag1] and @scheme[bag2] contain equivalent
elements @scheme[e1] and @scheme[e2] respectively, union adds
@scheme[e1] to the result in their place with a total number of
occurrences equal to the maximum of either @scheme[e1]'s occurrences
in @scheme[bag1] or @scheme[e2]'s occurrences in @scheme[bag2].}

@defproc[(intersection (bag1 bag?) (bag2 bag?)) bag?]{Produces a bag
containing all elements present in both @scheme[bag1] or
@scheme[bag2].  If @scheme[bag1] and @scheme[bag2] contain equivalent
elements @scheme[e1] and @scheme[e2] respectively, intersection adds
@scheme[e1] to the result in their place with a total number of
occurrences equal to the minimum of either @scheme[e1]'s occurrences
in @scheme[bag1] and @scheme[e2]'s occurrences in @scheme[bag2].}

@defproc[(difference (bag1 bag?) (bag2 bag?)) bag?]{Produces a bag
containing all elements of @scheme[bag1] not found in @scheme[bag2].
This means that if an element appears in @scheme[bag1] @scheme[n]
times and @scheme[bag2] @scheme[m] times, then the resulting bag will
have @scheme[(- n m)] copies of the element (and will not contain it
if @scheme[(>= m n)]).}

@subsection{Bag Relations}

These operations compare multiple bags.  As in
@secref["Subsec:BagCombinations"], multiple bags may only be
meaningfully compared if their notions of distinct elements are the
same.

@defproc[(subbag? (bag1 bag?) (bag2 bag?)) boolean?]{Reports whether
all elements in @scheme[bag1] are present in @scheme[bag2].  This
includes checking that the number of times the element appears in
@scheme[bag2] is at least as many as the number of times it appears in
@scheme[bag1].}

@defproc[(equal? (bag1 bag?) (bag2 bag?)) boolean?]{Reports whether
both bags contain the same elements with the same number of
occurrences.}

@section{Acknowledgements}

@itemize[

@item{The red-black trees implementation started as a port of
  Jean-Christophe Filliatre's Ocaml implementation.}

@item{Versions 1 and 2 of Galore and its documentation were written
  entirely by Jens Axel Soegaard.}

@item{Many thanks to Richard Cobbe and Sam Tobin-Hochstadt for helpful
  proofreading and functionality suggestions.}]

@section{Copyright and License}

For any questions not answered by this documentation, write to the PLT
Scheme mailing list at:
@link["mailto:plt-scheme@list.cs.brown.edu" "plt-scheme@list.cs.brown.edu"].

Alternately, contact one of the authors.  

This documentation and all source code of Galore are published under
the terms of the @link["http://www.gnu.org/licenses/lgpl.html"]{GNU
LGPL}.  See @filepath{license.txt} and @filepath{lgpl.txt} in the
Galore collection for more details.




@bibliography[

@bib-entry[#:key "Ada"
           #:title "Implementing Sets Efficiently in a Functional Language"
           #:author "Stephen Adams"
           #:url "http://groups.csail.mit.edu/mac/users/adams/BB/index.html"]

@bib-entry[#:key "Mar"
           #:title "Randomized Binary Search Trees"
           #:author "Conrado Martinez and Salvador Roura"
           #:url "http://portal.acm.org/citation.cfm?id=274812"]

@bib-entry[#:key "Oka"
           #:title "Purely Functional Data Structures"
           #:author "Chris Okasaki"
           #:url "http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#cup98"]

]

@(index-section)
